package com.java.multipledatasource.algorithm;

import java.util.Arrays;

/**
 * @author hu
 * @version 1.0
 * @date 2021/1/18 0018 下午 7:48
 * @description  ^  异或 <=> 无进位相加 异或与顺序无关 0 ^ N = N  ; N ^ N = 0
 */
public class Swap {
    public static void main(String[] args) {
//        swap(10, 8);
        int[] arr = {1, 2, 2,2,2, 6, 3,4,4,3,1};
//        findOddNumber(arr);
//        countBit1(3);
       // change(arr);
        System.out.println(1&3);
        exchange(arr);
    }

    public static void swap(int i, int j){
        System.out.println("before swap " + i + " " + j);

        i = i ^ j;
        j = i ^ j;
        i = i ^ j;

        System.out.println("after swap " + i + " " + j);
    }

    /**
     * 数组中只有一个数字出现奇数次 其他都出现偶数次
     * @param arr
     */
    public static void findOddNumber(int[] arr){
        for(int i = 1;  i < arr.length; i++){
            arr[0] = arr[i] ^ arr[0];
        }
        System.out.println(arr[0]);
    }

    /**
     * 数组中只有两个数字出现奇数次 其他都出现偶数次
     * @param arr
     */
    public static void findOddTimes2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        //eor = a ^ b;
        // eor != 0
        // eor 必有一个位置是1

        //提取最右侧的1    11001100 -> 00000100
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;

        for (int i = 0; i < arr.length; i++) {
            // 11011
            // 00001
            if ((arr[i] & rightOne )!= 0) {
               onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + "  " + (onlyOne ^ eor));
    }

    public static  void countBit1(int number){
        int count = 0;
        while (number != 0){
            int rightOne = number & (~number + 1);
            count++;
            number ^= rightOne;
            //1101100
         //  ^0000100
        }
        System.out.println("count " + count );
    }

    /**
     *输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
     * 使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
     * @param arr
     */
    public static void change(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
          if (arr[i] % 2 == 0) {
              for (int j = i + 1; j < arr.length; j++) {
                  if(arr[j] % 2 != 0) {
                      int temp = arr[i];
                      arr[i] = arr[j];
                      arr[j] = temp;
                      break;
                  }
              }
          }
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "  ");
        }
    }

    public static int[] exchange(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 != 0) {
                left++;
            }
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        for (int num : nums) {
            System.out.print(num + "   ");
        }
        return nums;
    }
}
